//给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。 
//
// 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：words = ["w","wo","wor","worl", "world"]
//输出："world"
//解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。
// 
//
// 示例 2： 
//
// 
//输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
//输出："apple"
//解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply" 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= words.length <= 1000 
// 1 <= words[i].length <= 30 
// 所有输入的字符串 words[i] 都只包含小写字母。 
// 
// Related Topics 字典树 数组 哈希表 字符串 排序 
// 👍 262 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LongestWordInDictionary {
    public static void main(String[] args) {
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 使用字典树Trim的解法
     */
    static class Solution {
        static int N = 30010, M = 26;
        static int[][] tr = new int[N][M];// 字典树
        static boolean[] isEnd = new boolean[N];// 结尾标记
        static int idx = 0;// 这只是一个链接位置标记，按照字典遍历字符串时只要能找到下一个位置就行，不用纠结
        void add(String s) {// 添加字符串
            int p = 0;
            for (char c : s.toCharArray()) {
                int u = c - 'a';
                if (tr[p][u] == 0) tr[p][u] = ++idx;// 此时说明第一次在这个位置添加字符，借助idx来完成
                p = tr[p][u];// p指向下一个位置
            }
            isEnd[p] = true;// 标记结束
        }
        boolean query(String s) {// 验证当前字符串是否符合字典要求
            int p = 0;
            for (char c : s.toCharArray()) {
                int u = c - 'a';
                p = tr[p][u];
                if (!isEnd[p]) return false;// 如果当前位置不是结尾，此字符串不满足要求
            }
            return true;
        }
        public String longestWord(String[] words) {
            // 初始化
            Arrays.fill(isEnd, false);
            for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
            idx = 0;
            String ans = "";

            for (String s : words) add(s);
            for (String s : words) {
                int n = s.length(), m = ans.length();
                if (n < m) continue;// 长度短的直接跳
                if (n == m && s.compareTo(ans) > 0) continue;// 相同长度比较字典序，要靠前的那个
                if (query(s)) ans = s;
            }
            return ans;
        }

        /**
         *  我自己写的方法，使用的是Set和排序
         */
        public String longestWord2(String[] words) {
            // 使用Set保存所有的words包括空串
            Set<String> set = new HashSet<>(Arrays.asList(words));
            set.add("");

            // 对words进行排序，长度大的在最后，长度相同时字典序小的在后边，便于之后的遍历
            Arrays.sort(words,(a, b) -> {
                if (a.length() == b.length()){
                    return b.compareTo(a);
                }else return a.length() - b.length();
            });

            // 反向遍历所有word，如果当前单词满足要求直接返回
            for (int i = words.length - 1; i >= 0 ; i--) {
                StringBuilder s = new StringBuilder(words[i]);
                boolean flag = true;
                while (s.length() > 0){
                    if (!set.contains(s.deleteCharAt(s.length() - 1).toString())){
                        flag = false;
                        break;
                    }
                }
                if (flag) return words[i];
            }

            // 都不满足要求返回空串
            return "";
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}